package me.chan.sort;

import me.chan.util.SortUtil;

import static me.chan.util.SortUtil.exch;
import static me.chan.util.SortUtil.less;
/**
 * Created by JanGin on 2017/9/10.
 */
public class ShellSort {

    private ShellSort(){}

    public static void sort(Comparable[] a) {
        int len = a.length;
        int h = 1;
        while (h <= len/3 )
            h = h * 3 + 1;

        while (h >= 1) {
            for (int i=h; i < len; i++) {
                for (int j=i; j >= h && less(a[j], a[j - h]); j-=h) {
                    exch(a, j, j - h);
                }
            }
            h /= 3;
        }
    }


    public static void main (String[] args) {

        Comparable[] str = {'S', 'H', 'E', 'L', 'L', 'S', 'O', 'R', 'T', 'E',
                                'X', 'A', 'M', 'P', 'L', 'E'};
        SortUtil.show(str);

        sort(str);

        SortUtil.show(str);
    }
}
